package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * https://leetcode.com/problems/24-game/
 * You have 4 cards each containing a number from 1 to 9.
 * You need to judge whether they could operated through *, /, +, -, (, )
 * to get the value of 24.
 * <p>
 * 直接暴力遍历, 不也就4^3种情况么----- 并不是, 操作符有4^3种, 数字呢,,,...
 * 操作符位置, 4种
 * 数字摆放, 4!种
 * total=6144种
 * ---以上算法也不对, 不是排列问题, 会重复
 *
 * @author tzp
 * @since 2020/11/3
 */
public class LC679 implements Backtracking {
    boolean result = false;

    public boolean judgePoint24(int[] nums) {
        LinkedList<Float> list = new LinkedList<>();
        for (int num : nums) {
            list.add((float) num);
        }
        backtracing(list);
        return result;
    }

    public void backtracing(List<Float> remain) {
        if (remain.size() == 2) {
            result = Math.abs(remain.get(0) + remain.get(1) - 24) <= 1e-4
                    || Math.abs(remain.get(0) - remain.get(1) - 24) <= 1e-4
                    || Math.abs(remain.get(0) * remain.get(1) - 24) <= 1e-4
                    || Math.abs(remain.get(0) / remain.get(1) - 24) <= 1e-4;//小技巧
        } else if (remain.size() >= 2) {
            for (int i = 0; i < remain.size(); i++) {
                for (int j = i + 1; j < remain.size(); j++) {//选择两个数字
                    Float vi = remain.remove(i);
                    Float vj = remain.remove(j - 1);//make choice
                    //选择一种符号
                    {// +
                        remain.add(vi + vj);
                        backtracing(remain);
                        if (result) return;
                        remain.remove(remain.size() - 1);
                    }
                    {// -
                        remain.add(vi - vj);
                        backtracing(remain);
                        if (result) return;
                        remain.remove(remain.size() - 1);
                    }
                    {// -
                        remain.add(vj - vi);
                        backtracing(remain);
                        if (result) return;
                        remain.remove(remain.size() - 1);
                    }
                    {// *
                        remain.add(vi * vj);
                        backtracing(remain);
                        if (result) return;
                        remain.remove(remain.size() - 1);
                    }
                    {// /
                        if (vj != 0) {
                            remain.add(vi / vj);
                            backtracing(remain);
                            if (result) return;
                            remain.remove(remain.size() - 1);
                        }
                    }
                    {// /
                        if (vi != 0) {
                            remain.add(vj / vi);
                            backtracing(remain);
                            if (result) return;
                            remain.remove(remain.size() - 1);
                        }
                    }
                    remain.add(i, vi);//reset choice
                    remain.add(j, vj);
                }
            }
        } else {
            throw new RuntimeException();
        }
    }

    public static void main(String[] args) {
//        System.out.println(new LC679().judgePoint24(new int[]{4, 1, 8, 7}));//true
//        System.out.println(new LC679().judgePoint24(new int[]{1, 2, 1, 2}));//false
//        System.out.println(new LC679().judgePoint24(new int[]{8, 1, 6, 6}));//true 6/(1-(6/8))
        System.out.println(new LC679().judgePoint24(new int[]{3, 3, 8, 8}));//true 8/(3-(8/3))

    }
}
